/*
题目: 两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

https://leetcode.cn/problems/delete-operation-for-two-strings/
 */
public class MinDistanceString {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        // 让 word1[:i] 和 Word2[:j] 相等的最少删除步数
        int[][] dp = new int[m + 1][n + 1];
        // 两个字符串都为空的最小操作步数为 0
        // 初始化: 任意一个串 变成 空串 的次数都是 长度大小
        for (int i = 1; i <= m; i ++)   dp[i][0] = i;
        for (int i = 1; i <= n; i ++)   dp[0][i] = i;

        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                // 如果相等, 相等于没有这两个 字符
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else { // 如果不相等, 相当于 分别删除 [新增的两个字符之一] 的最小值
                    dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}
